#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

vector<TreeNode*> gettrees(int start, int end)
{
    if (start > end) return { nullptr };
    vector<TreeNode*> res;
    for (int i = start; i <= end; i++)
    {
        vector<TreeNode*> ltrees = gettrees(start, i - 1);
        vector<TreeNode*> rtrees = gettrees(i + 1, end);

        for (auto& left : ltrees)
            for (auto& right : rtrees)
            {
                TreeNode* cur = new TreeNode(i);
                cur->left = left;
                cur->right = right;
                res.emplace_back(cur);
            }
    }
    return res;
}

vector<TreeNode*> generateTrees(int n) {
    if (!n)  return {};
    return gettrees(1, n);
}